/*
 * This file is part of the Sx Framework Library.
 * 
 * Copyright (C) 2013 University of Colorado Denver
 * <min.choi@ucdenver.edu> <shane.transue@ucdenver.edu>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy 
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
 * copies of the Software, and to permit persons to whom the Software is 
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in 
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 * DEALINGS IN THE SOFTWARE.
 */
#ifndef SX_ARRAY_LIST_H
#define SX_ARRAY_LIST_H

#include <iostream>
#include <iterator>

/*
 * The implementation class of the ArrayList cannot be hidden in an opaque
 * pointer due to the template definition of the class; however the
 * implementation of the ArrayList interface can be facilitated through the
 * standard vector container.
 */
#include <vector>
#include <algorithm>

namespace Sx {
namespace Util {

/*
 * This vector array class implements a basic list wrapper around a
 * standard vector type. Type and allocator type are simply passed through.
 * Many simplistic utility functions have been added to provide a simple
 * interface to a vector list. Standard library iterators are not supported;
 * this array can however be converted to a standard vector for additional
 * standard algorithms. The default standard allocator is provided as the
 * default allocator type.
 */
template <typename T, typename allocator = std::allocator<T> >
class ArrayList {
public:
	/*
	 * Definition of the array type implementation. This implementation
	 * only has to be changed in this one location to support a different
	 * internal array implementation. This implementation however must
	 * support iterators following the standard library iterator
	 * interface since this ArrayList class provides that same interface.
	 */
	typedef std::vector<T, allocator> VectorType;
	typedef typename VectorType::iterator ArrayIterator;
	typedef typename VectorType::const_iterator ConstArrayIterator;
	typedef typename VectorType::reference ArrayReference;
	typedef typename VectorType::const_reference ConstArrayReference;

	ArrayList();

	/*
	 * Create a new ArrayList with a predefined length given by size.
	 */
	ArrayList(unsigned int size);

	/* 
	 * Creates a new ArrayList with the provided size and initializes each
	 * element with the provided value.
	 */
	ArrayList(unsigned int size, T value);

	/*
	 * Copy another ArrayList assuming that type and allocator are the same.
	 */
	ArrayList(const ArrayList<T, allocator>& a);

	/*
	 * Create an ArrayList that contains T data of length size.
	 */
	ArrayList(const T* data, unsigned int size);
	~ArrayList();

	/*
	 * This function allocates an empty ArrayList of the given size. If any
	 * information is inside of this ArrayList when this function is called
	 * it will be erased.
	 */
	void allocate(unsigned int size);

	/*
	 * Returns a point to the data contained in this ArrayList.
	 */
	T* data();

	/*
	 * Converts this ArrayList to a standard vector.
	 */
	operator std::vector<T, allocator> ();

	/*
	 * Returns a constant pointer to the data contained in this ArrayList.
	 */
	const T* constData() const;

	/*
	 * The following functions append the provided data to the end of 
	 * this ArrayList.
	 */
	void add(const T& data);
	void append(const T& data);
	void addLast(const T& data);
	void push_back(const T& data);

	/*
	 * The following functions add the provided data to the beginning of
	 * this ArrayList.
	 */
	void addFirst(const T& data);
	void push_front(const T& data);

	/*
	 * The following function removes the first item from this ArrayList.
	 */
	void removeFirst();
	
	/*
	 * Removes all entries from this ArrayList that match the definition of
	 * the provided predicate. An example of a predicate is as shown below:
	 *  bool predicate(int a) { if ( a < n ) return true; return false; }
	 * This predicate would remove all int entries from the array list
	 * that are less than n.
	 */
	bool removeIf(bool (*predicate)(const T));

	/*
	 * The following function removes the first item from this ArrayList.
	 */
	void pop_front();

	/*
	 * The following functions remove the last item from this ArrayList.
	 */
	void removeLast();
	void pop_back();

	/*
	 * Clear all of the items out of the ArrayList.
	 */
	virtual void clear();
	virtual void empty();

	/*
	 * Inserts the provided data into this ArrayList at the provided index.
	 */
	bool insert(unsigned int index, const T& data);

	/*
	 * Sets the data of the item at the provided index. The data at the index
	 * position is overwritten.
	 */
	bool set(unsigned int index, const T& data);

	/*
	 * Remove the item at the specified index.
	 */
	bool removeAt(unsigned int index);

	/*
	 * Remove an exact element from this ArrayList.
	 */
	bool remove(const T& data);

	/*
	 * Erases the elements contained in this ArrayList from begin to end.
	 */
	ArrayIterator erase(const ArrayIterator& begin, const ArrayIterator& end);

	/*
	 * Erases the element at the provided iterator position.
	 */
	ArrayIterator erase(const ArrayIterator& position);

	/*
	 * Inserts the span defined by the begin and end iterators at the provided
	 * position.
	 */
	void insert(const ArrayIterator& position, ArrayIterator& begin, ArrayIterator& end);

	/*
	 * Reserves this number of items in the internal array representation.
	 */
	void reserve(unsigned int count);

	void resize(unsigned int count);

	/*
	 * Determines if the provided data is present in this ArrayList. If the
	 * provided data item is found in this ArrayList then the function will
	 * return true; otherwise it will return false.
	 */
	bool contains(const T& data) const;

	/*
	 * If this ArrayList does not contain any elements this function will
	 * return true; otherwise it will return false.
	 */
	bool isEmpty() const;
	
	/*
	 * The following functions return the index of the first occurance of 
	 * the provided data.
	 */
	unsigned int indexOf(const T& data);
	unsigned int find(const T& data);

	/*
	 * Returns the internal capacity currently allocated for this ArrayList.
	 */
	unsigned int capacity() const;

	/*
	 * Returns the number of elements in contained in this ArrayList.
	 */
	virtual unsigned int size() const;

	/*
	 * Provides a native pointer to the data contained in this ArrayList.
	 */
	operator T* ();

	/*
	 * Provides a constant native pointer to the data contained in
	 * this ArrayList.
	 */
	operator const T* ();

	/*
	 * The following functions can be used to retrieve an element from this
	 * ArrayList at the provided index position.
	 */
	const T& get(unsigned int index);
	T& operator [] (int index);
	const T& operator [] (int index) const;

	/*
	 * Assignment operator for copying an ArrayList.
	 */
	ArrayList<T, allocator>& operator = (const ArrayList<T, allocator>& a);

	bool removeIndices(ArrayList<unsigned int>& indices);
	static ArrayList<T, allocator> RemoveIndices(const ArrayList<T>& data, ArrayList<unsigned int>& indices);

	/*
	 * Provides a basic textual representation of the elements contained in
	 * this ArrayList.
	 */
	friend std::ostream& operator << (std::ostream& out, const ArrayList& arrayList) {
		for ( unsigned int i = 0; i < arrayList.size(); i++ ) out << arrayList[i];
		return out;
	}

	/*
	 * Following the std iterator interface, the internal implementation
	 * must provide the required types and functions utilized by the
	 * standard library.
	 */
	ArrayReference at(unsigned int index);
	ArrayIterator begin();
	ArrayIterator end();
	ConstArrayIterator begin() const;
	ConstArrayIterator end() const;

protected:
	VectorType imp;
};

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::ArrayList() {
	this->imp = VectorType();
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::ArrayList(unsigned int size) {
	this->imp = VectorType(size);
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::ArrayList(unsigned int size, T value) {
	this->imp = VectorType(size, value);
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::ArrayList(const ArrayList<T, allocator>& a) {
	this->imp = a.imp;
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::ArrayList(const T* data, unsigned int size) {
	this->imp = VectorType(size);
	for ( unsigned int i = 0; i < size; i++ ) {
		this->imp[i] = data[i];
	}
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::~ArrayList() {
	this->imp.clear();
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::allocate(unsigned int size) {
	this->imp = VectorType(size);
}

template <typename T, typename allocator>
T* Sx::Util::ArrayList<T, allocator>::data() {
	return &this->imp[0];
}

/*
 * This would have to be used if the internal vector is not a standard
 * vector type. Currently the standard vector is being returned for 
 * speed considerations (Assuming RVO is considered)
 *  std::vector<T, allocator> a(this->imp.size());
 *  for ( unsigned int i = 0; i < this->imp.size(); i++ )
 *  a[i] = this->imp[i];
 *  return a;
 */
template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::operator std::vector<T, allocator> () {
	return this->imp;
}

template <typename T, typename allocator>
const T* Sx::Util::ArrayList<T, allocator>::constData() const {
	return &this->imp[0];
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::add(const T& data) {
	this->imp.push_back(data);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::append(const T& data) {
	this->imp.push_back(data);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::addLast(const T& data) {
	this->imp.push_back(data);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::push_back(const T& data) {
	this->imp.push_back(data);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::addFirst(const T& data) {
	this->imp.insert(this->imp.begin(), data);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::push_front(const T& data) {
	this->imp.insert(this->imp.begin(), data);
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::insert(unsigned int index, const T& data) {
	if ( index >= this->imp.size() ) {
		std::cerr << "[ArrayList:insert] Error: Index out of bounds: " << index << std::endl;
		return false;
	}
	this->imp.insert(this->imp.begin() + index, data);
	return true;
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::set(unsigned int index, const T& data) {
	if ( index >= this->imp.size() ) {
		std::cerr << "[ArrayList:set] Error: Index out of bounds: " << index << std::endl;
		return false;
	}

	this->imp[index] = data;
	return true;
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::removeAt(unsigned int index) {
	if ( index >= this->imp.size() ) return false;
	this->imp.erase(this->imp.begin() + index);
	return true;
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::remove(const T& data) {
	return this->removeAt(this->find(data));
}

template <typename T, typename allocator>
typename Sx::Util::ArrayList<T, allocator>::ArrayIterator Sx::Util::ArrayList<T, allocator>::erase(const ArrayIterator& begin, const ArrayIterator& end) {
	return this->imp.erase(begin, end);
}

template <typename T, typename allocator>
typename Sx::Util::ArrayList<T, allocator>::ArrayIterator Sx::Util::ArrayList<T, allocator>::erase(const ArrayIterator& position) {
	return this->imp.erase(position);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::insert(const ArrayIterator& position, ArrayIterator& begin, ArrayIterator& end) {
	this->imp.insert(position, begin, end);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::reserve(unsigned int count) {
	this->imp.reserve(count);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::resize(unsigned int count) {
	this->imp.resize(count);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::removeFirst() {
	this->imp.erase(this->imp.begin());
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::removeIf(bool (*predicate)(const T)) {
	if ( predicate == nullptr ) {
		std::cout << "[ArrayList:removeIf] Error: null predicate function." << std::endl;
		return false;
	}

	this->imp.erase(std::remove_if(this->imp.begin(), this->imp.end(), predicate), this->imp.end());
	return true;
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::removeLast() {
	this->imp.erase(this->imp.end() - 1);
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::pop_front() {
	this->removeFirst();
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::pop_back() {
	this->removeLast();
}

template <typename T, typename allocator>
unsigned int Sx::Util::ArrayList<T, allocator>::indexOf(const T& data) {
	return this->find(data);
}

template <typename T, typename allocator>
unsigned int Sx::Util::ArrayList<T, allocator>::find(const T& data) {
	VectorType::iterator i = std::find(this->imp.begin(), this->imp.end(), data);
	if ( i == this->imp.end() ) return -1;
	return i - this->imp.begin();
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::contains(const T& data) const {
	if ( std::find(this->imp.begin(), this->imp.end(), data) != this->imp.end() ) return true;
	return false;
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::clear() {
	this->imp.erase(this->imp.begin(), this->imp.end());
}

template <typename T, typename allocator>
void Sx::Util::ArrayList<T, allocator>::empty() {
	this->imp.erase(this->imp.begin(), this->imp.end());
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::isEmpty() const {
	if ( this->imp.size() == 0 ) return true;
	return false;
}

template <typename T, typename allocator>
unsigned int Sx::Util::ArrayList<T, allocator>::capacity() const {
	return this->imp.capacity();
}

template <typename T, typename allocator>
unsigned int Sx::Util::ArrayList<T, allocator>::size() const {
	return this->imp.size();
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::operator T* () {
	return &this->imp[0];
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>::operator const T* () {
	return &this->imp[0];
}

template <typename T, typename allocator>
const T& Sx::Util::ArrayList<T, allocator>::get(unsigned int index) {
	if ( index >= this->imp.size() )
		std::cerr << "[ArrayList:get] Error: Index out of bounds: " << index << std::endl;
	return this->imp[index];
}

template <typename T, typename allocator>
T& Sx::Util::ArrayList<T, allocator>::operator [] (int index) {
	if ( static_cast<unsigned int>(index) >= this->imp.size() )
		std::cerr << "[ArrayList:operator[]] Error: Index out of bounds: " << index << std::endl;
	return this->imp[index];
}

template <typename T, typename allocator>
const T& Sx::Util::ArrayList<T, allocator>::operator [] (int index) const {
	if ( static_cast<unsigned int>(index) >= this->imp.size() )
		std::cerr << "[ArrayList:operator[]] Error: Index out of bounds: " << index << std::endl;
	return this->imp[index];
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator>& Sx::Util::ArrayList<T, allocator>::operator = (const ArrayList<T, allocator>& a) {
	if ( this == &a ) return *this;
	this->imp = a.imp;
	return *this;
}

template <typename T, typename allocator>
bool Sx::Util::ArrayList<T, allocator>::removeIndices(ArrayList<unsigned int>& indices) {
	if ( indices.isEmpty() ) return false;

    std::vector<T, allocator> ret;
    ret.reserve(this->imp.size() - indices.size());
    std::sort(indices.begin(), indices.end());

	std::vector<T, allocator>::const_iterator itBlockBegin = this->imp.begin();
    for ( std::vector<unsigned int>::const_iterator it = indices.begin(); it != indices.end(); ++ it ) {
        std::vector<T, allocator>::const_iterator itBlockEnd = this->imp.begin() + *it;
        if ( itBlockBegin != itBlockEnd ) {
			std::copy(itBlockBegin, itBlockEnd, std::back_inserter(ret));
		}
		itBlockBegin = itBlockEnd + 1;
	}

    if ( itBlockBegin != this->imp.end() ) {
		std::vector<T, allocator>::const_iterator end = this->imp.end();
		std::copy(itBlockBegin, end, std::back_inserter(ret));
	}

	this->clear();
	this->imp = VectorType(ret);
	return true;
}

template <typename T, typename allocator>
Sx::Util::ArrayList<T, allocator> Sx::Util::ArrayList<T, allocator>::RemoveIndices(const ArrayList<T>& data, ArrayList<unsigned int>& indices) {
	if ( indices.isEmpty() ) return data;

    std::vector<T> ret;
    ret.reserve(data.size() - indices.size());
    std::sort(indices.begin(), indices.end());

	std::vector<T>::const_iterator itBlockBegin = data.begin();
    for ( std::vector<size_t>::const_iterator it = indices.begin(); it != indices.end(); ++ it ) {
        std::vector<T>::const_iterator itBlockEnd = data.begin() + *it;
        if ( itBlockBegin != itBlockEnd ) {
			std::copy(itBlockBegin, itBlockEnd, std::back_inserter(ret));
		}
		itBlockBegin = itBlockEnd + 1;
	}

    if(itBlockBegin != data.end()) {
		std::copy(itBlockBegin, data.end(), std::back_inserter(ret));
	}

	ArrayList<T, allocator> finalArray;
	finalArray.imp = VectorType(ret);
	return finalArray;
}

template <typename T, typename allocator>
typename Sx::Util::ArrayList<T, allocator>::ArrayReference Sx::Util::ArrayList<T, allocator>::at(unsigned int index) {
	return this->imp.at(index);
}

template <typename T, typename allocator>
typename Sx::Util::ArrayList<T, allocator>::ArrayIterator Sx::Util::ArrayList<T, allocator>::begin() {
	return this->imp.begin();
}

template <typename T, typename allocator>
typename Sx::Util::ArrayList<T, allocator>::ArrayIterator Sx::Util::ArrayList<T, allocator>::end() {
	return this->imp.end();
}

template <typename T, typename allocator>
typename Sx::Util::ArrayList<T, allocator>::ConstArrayIterator Sx::Util::ArrayList<T, allocator>::begin() const {
	return this->imp.begin();
}

template <typename T, typename allocator>
typename Sx::Util::ArrayList<T, allocator>::ConstArrayIterator Sx::Util::ArrayList<T, allocator>::end() const {
	return this->imp.end();
}

}

}

#endif
